package org.example.myleet.rosalind.motz;

import org.example.myleet.rosalind.utils.FastaReader;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
//        solution.solve(FastaReader.parseFastaInput(">Rosalind_57\n" +
//                "AUAU\n").get(0).getSequence());
        solution.solve(FastaReader.parseFastaInput(">Rosalind_6951\n" +
                "GACCUCUAUGUAUGCGAGGCACAUCUCUGAUUCUCUCGUGUCCGGAUGUGACUGGGCUCC\n" +
                "UCUCUUUCGGGGUGAGACCGCCACUCGGACAAGUGUGAUGUCUAUUAAAUCUGCUAGUAC\n" +
                "GAAGAGUUAGAACCCAGGCGUGGUGCACAAGGACGACAACCCAGCGCGUCAGGUAUUUGG\n" +
                "UCUGUAGUCUUAAAUAGGGACCCUGCAGGUUGAGAUCAAGCAAUCAUGGAUAUGUCUCUG\n" +
                "GUACAGCUGA\n").get(0).getSequence());
    }

    private static final int MOD_BASE = 1000000;

    private Map<String, Integer> memo = new HashMap<>();

    public void solve(String seq) {
        int motzkinNumber = calMotzkinNumber(seq);
        System.out.println(motzkinNumber);
    }

    private int calMotzkinNumber(String seq) {
        Integer res = memo.get(seq);
        if (null != res) {
            return res;
        }
        if (seq.length() < 2) {
            return 1;
        }
        long motzkinNumber = 0;
        List<Integer> matchIndices = getChar0MatchIndices(seq);
        for (int index : matchIndices) {
            int leftMotzkinNumber = calMotzkinNumber(seq.substring(1, index));
            int rightMotzkinNumber = calMotzkinNumber(seq.substring(index + 1));
            motzkinNumber += (long) leftMotzkinNumber * (long) rightMotzkinNumber;
            motzkinNumber %= MOD_BASE;
        }
        int prevMotzkinNumber = calMotzkinNumber(seq.substring(1));
        motzkinNumber += prevMotzkinNumber;
        motzkinNumber %= MOD_BASE;
        int m = (int) motzkinNumber;
        memo.put(seq, m);
        return m;
    }

    private List<Integer> getChar0MatchIndices(String seq) {
        List<Integer> res = new ArrayList<>(seq.length() - 1);
        char c0 = seq.charAt(0);
        for (int i = 1; i < seq.length(); ++i) {
            char c = seq.charAt(i);
            if (c0 == 'A' && (c == 'U' || c == 'T')) {
                res.add(i);
            } else if (c0 == 'U' && c == 'A') {
                res.add(i);
            } else if (c0 == 'C' && c == 'G') {
                res.add(i);
            } else if (c0 == 'G' && c == 'C') {
                res.add(i);
            }
        }
        return res;
    }
}
